COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	ullman.not[w83,jmc]	Notes on "On the semantics of updates in databases"
C00006 00003	A try at formalizing their theory:
C00011 ENDMK
C⊗;
ullman.not[w83,jmc]	Notes on "On the semantics of updates in databases"

"On the Semantics of Updates in Databases - Preliminary report"
by Ronald Fagin, Jeffrey Ullman, Moshe Vardi
(undated but 1983 January)

1. There is a similarity between their idea of making a minimal change
in a database in order to update it and my idea of minimizing a
sentence relative to an axiom.  It seems unlikely that one is
reducible to the other.

2. Their discussion is in terms of models, and it is interesting
to ask whether their idea has a syntactic counterpart - just
as circumscription is the syntactic counterpart of minimal models.
It would seem that this would require formalizing enough of the
metamathematics to be able to compare two sets of changes to see
if one is included in the other.  But wait!  We might be able to
get by by asking merely that one imply the other.

3. Their idea of distinguishing the theory from its closure and
then putting priorities on the sentences in the database puts more
structure on the database than is its consequences.  My intuition
is that still more structure is required.  The idea of complementary
views is a specialization of the idea of frame or co-ordinate system
that is used with circumscription and in discussions of the frame
problem.

x. They take the unique names hypothesis for granted, and this
means that they cannot accept an update that says that two
entities with distinct names are, after all, the same.  We can
imagine a convention that children are listed by first name
and that the children of distinct employees are assumed distinct
unless the two employees are spouses in which case children with
the same first name are assumed the same, unless the contrary is
specifically stated.

4. Their idea about required relations between the original and
updated databases can stand elaboration.  An event that has occurred
cannot unoccur.  Jefferson would rather believe that two Yankee
scientists would lie than that stones would fall from the sky.

5. AI examples will help; ie. update states of knowledge.
e.g. "knows about cars".

6. They should allow attachments of computable functions to
databases.

7. They don't discuss the consequences of a fact that a view may
have many complementary views.  Choosing a preferred complementary
view is a special case of choosing a co-ordinate system.
A try at formalizing their theory:

Ontology:

	1. Databases: We use variables db, db0, db1, etc. to range over
databases and have database constants Db, Db0, etc.  A database cosntant
may also be given a a set of sentences.

	2. Worlds: Variables w, w0, etc. and constants W, W0, etc.

Relations:

	1. holds(db,w)

	2. db1 ≤ db2 ⊃ ∀w.holds(db2,w) ⊃ holds(db1,w)

I don't think we want the converse or we will find ourselves identifying
a database with its closure.

Functions:

	1. If we have  db1 ≤ db2,  then  db2 - db1  is defined.

	2. conjunction(db)  is a database with a single formula
that is the conjunction of all the formulas in  db.  However,  conjunction(db)
no longer distinguishes the individual components, so it is possible to
have

	db1 ≠ db2 ∧  conjunction(db1) = conjunction(db2).

It might be reasonable to identify  conjunction(db)  with the logical closure
of  db.  We have

	conjunction(conjunction(db)) = conjunction(db).

	3. db1 + db2  is defined but may be inconsistent.

Definition:

	1. consistent(db) ≡ ∃w.holds(db,w)

Remarks:

	1. Single sentences can be identified with certain databases.
They satisfy  conjunction(db) = db.

	The FUV (Fagin, Ullman, Vardi) operations of inserting and
deleting sentences in databases correspond to operations

	db1 ++ db2

and

	db1 -- db2.

However, these give rise to sets of databases rather than single
databases.

	We have approximately

	db ε (db1 -- db2) ≡ consistent(db) 
			∧ ∀s.s ε db ⊃ s ε db1 ∧ ¬(s ε db2)
			∧ [∀db'.[∀s.s ε db' ⊃ s ε db1 ∧ ¬(s ε db2)] ⊃ db' ≤ db].

This doesn't seem to be quite what we want, because it uses sentences
as members of databases.

*****

Modified try.

	We have another operation  db1∩db2  and we have the empty database
{}.  We can say

	db ε (db1 -- db2) ≡ consistent(db)
			∧ db ∩ db2 = {}
			∧ db ⊂ db1
			∧ ∀db'.consistent(db') ∧ db' ∩ db2 = {} ∧ db' ⊂ db1
				⊃ db' ⊂ db.

Adding this operation means that we are modelling databases very closely
on sets of sentences.

*****

More remarks:

	We can add a database parameter to the relations and
make functions out of the modified relations to a domain of
propositions.
	Thus we could have

	R(Gauss,Yoni,Math,Db0)

as an object and

	holds(R(Gauss,Yoni,Math,Db0),W0).

It isn't clear that we want to go this far in reification.  No, it
seems better to have

	R(Gauss,Yoni,Math,Db0)

as a sentence and to have

	holds(Db0,W0)

as another sentence.

	Incidentally, our objective in this whole exercise is to
axiomatize sufficiently so that it will be a theorem that a new
database is a minimal update of another with respect to an insertion
or deletion of a sentence.  In this case, the sentences had better
be objects.